#include<iostream>
#include<vector>

/*给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。*/

 int FindIndex(const std::vector<int>& array,int tar)
 {
    int left = 0;
    int right = array.size();
    int mid = (left + right) / 2;
    while(left < right)
    {
        if(array[mid] == tar)
        {
            return mid;
        }
        else if(array[mid] > tar)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
        mid = (left + right) / 2;
    }
    return mid;
 }

void test()
{
    std::vector<int> s = {1,2,3,4,6,7,8,9,23,35};
    int ret = FindIndex(s,7);
    std::cout << "7的下标为:" << ret << std::endl;
}

int main()
{
    test();

    return 0;
}